package leetcode;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

//子数组最小乘积最大值
public class Code008_MaxSumMinProduct {


    public static int maxSumMinProduct(int[] nums) {
        // 单调栈
        LinkedList<Integer> stack = new LinkedList<>();
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                int cur = stack.pop();
                int sum = 0;
                int left = i;
                if (stack.peek() != null) {
                    left = stack.peek();
                }
                for (int j = left + 1; j < i; j++) {
                    sum += nums[j];
                }
                sum = sum * nums[cur];
                maxSum = Math.max(sum, maxSum);

            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            int sum = 0;
            int left = cur;
            if (stack.peek() != null) {
                left = stack.peek();
            }
            for (int j = left + 1; j <= cur; j++) {
                sum += nums[j];
            }
            sum = sum * nums[cur];
            maxSum = Math.max(sum, maxSum);
        }

        return maxSum;
    }


    public static int maxSumMinProduct2(int[] nums) {
        //前缀和数组
        // nums[i] + ... + nums[j] = preSum[j+1] - preSum[i]
        int n = nums.length;
        long[] preSum = new long[n + 1];
        preSum[0] = 0;
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        long maxSum = Long.MIN_VALUE;
        Deque<ArrayList<Integer>> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek().get(0)]) {
                ArrayList<Integer> pop = stack.pop();
                // left 指的是离当前数最近的最小的数位置
                int left = !stack.isEmpty() ? stack.peek().get(stack.peek().size()-1) + 1 : 0;
                int right = i - 1;
                long sum = nums[pop.get(0)] * (preSum[right + 1] - preSum[left]);
                maxSum = Math.max(sum, maxSum);
            }
            if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {  // 相同元素放一起
                stack.peek().add(i);
            } else { // 第一次加入
                ArrayList<Integer> node = new ArrayList<>();
                node.add(i);
                stack.push(node);
            }
        }
        while (!stack.isEmpty()) {
            ArrayList<Integer> pop = stack.pop();
            int left = !stack.isEmpty() ? stack.peek().get(stack.peek().size()-1) + 1 : 0;
            int right = n -1;

            long sum = nums[pop.get(0)] * (preSum[right + 1] - preSum[left]);
            maxSum = Math.max(sum, maxSum);
        }
        long mod = (long) 1e9 + 7;
        return (int)(maxSum % mod);
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 3, 2, 2, 2, 1, 5, 1, 5};
        int[] nums2 = {2, 5, 4, 2, 4, 5, 3, 1, 2, 4};
        int[] nums3 = {36,9,13,27,43,25,44,48,12,40,37,20,26,36,1,20,19,14,28,38,39,42,21,30,29,29,44,14,33,31,48,11,43,6,19,33,43,41,40,22,6,49,16,44,20,15,13,10,2,3,16,31,40,50,5,30,27,41,37,13,46,45,25,32,26,16,10,42,45,1,49,50,7,50,28,15,12,45,34,30,4,36,16,8,30,9,30,43,34,36,39,21,49,29,40,47,33,28,36,29};
        int res = maxSumMinProduct2(nums2);
        System.out.println(res);
        int res2 = maxSumMinProduct2(nums3);
        System.out.println(res2);
    }
}
